백준 17404번

RGB거리 2

Posted by ChoiCube84 on February 08, 2024 · 8 mins read
프로그래밍 문제풀이

백준 17404번

오늘 풀어본 문제는 백준의 17404번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

RGB거리에는 집이 $N$ 개 있다. 거리는 선분으로 나타낼 수 있고, $1$ 번 집부터 $N$ 번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

$1$ 번 집의 색은 $2$ 번, $N$ 번 집의 색과 같지 않아야 한다. $N$ 번 집의 색은 $N-1$ 번, $1$ 번 집의 색과 같지 않아야 한다. $i$ $(2 \le i \le N-1)$ 번 집의 색은 $i-1$, $i+1$ 번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 $N$ $(2 \le N \le 1,000)$ 이 주어진다. 둘째 줄부터 $N$ 개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 $1,000$ 보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

풀이과정

1번째 시도

문제를 해결하기 위해 사용한 방식은 다음과 같다.

  1. 2차원으로 된 DP 배열을 만든다. 첫 번째 인덱스는 현재 색칠할 집을, 두 번째 인덱스는 첫 번째 집이 어떻게 색칠되었고, 이번 집을 어떻게 색칠할 것인가를 나타낸다. 저장된 값은 해당 상황에 도달하기 위해 필요한 최소 비용을 나타내며, 도달이 불가능한 경우는 INT_MAX 로 설정된다.

  2. 반복문을 활용하여 DP 배열을 채운다. 점화식은 이전의 집이 현재 색칠할 색과 다르면서 처음 집의 색이 동일한 경우의 최소값과, 현재 집을 원하는 색깔로 칠하는 비용의 합으로 구성된다.

  3. 마지막 집까지 색칠되었을 때, 가능한 비용들 중 처음 집과 색깔이 다른 경우들 중의 최소값을 구하여 출력한다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    vector<vector<int>> price(N, vector<int>(3, 0));
    vector<vector<int>> dp(N, vector<int>(9, INT_MAX));

    for (int i=0; i<N; i++) {
        cin >> price[i][0] >> price[i][1] >> price[i][2];
    }

    // dp[i][0]: Red Start, Red Now
    // dp[i][1]: Red Start, Green Now
    // dp[i][2]: Red Start, Blue Now
    // dp[i][3]: Green Start, Red Now
    // dp[i][4]: Green Start, Green Now
    // dp[i][5]: Green Start, Blue Now
    // dp[i][6]: Blue Start, Red Now
    // dp[i][7]: Blue Start, Green Now
    // dp[i][8]: Blue Start, Blue Now

    dp[0][0] = price[0][0];
    dp[0][4] = price[0][1];
    dp[0][8] = price[0][2];

    for (int i=1; i<N; i++) {
        for (int base=0; base<9; base+=3) {
            int prev0 = min(dp[i-1][base + 1], dp[i-1][base + 2]);
            int prev1 = min(dp[i-1][base + 0], dp[i-1][base + 2]);
            int prev2 = min(dp[i-1][base + 0], dp[i-1][base + 1]);

            dp[i][base + 0] = prev0 == INT_MAX ? INT_MAX : prev0 + price[i][0];
            dp[i][base + 1] = prev1 == INT_MAX ? INT_MAX : prev1 + price[i][1];
            dp[i][base + 2] = prev2 == INT_MAX ? INT_MAX : prev2 + price[i][2];
        }
    }

    int result = min({dp[N-1][1], dp[N-1][2], dp[N-1][3], dp[N-1][5], dp[N-1][6], dp[N-1][7]});

    cout << result;

    return 0;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

이번 문제를 성공적으로 풀어내면서, CLASS 5 의 모든 문제를 풀어내는데 성공하였다!

(수정: 2024-06-09) 라고 생각했는데 아니었다! 솔브드 업데이트로 인해 아직 더 풀 문제들이 몇 개 남아있다. 아래의 감상은 굳이 지우진 않고 남겨두겠다.

길고 어려운 여정이었다. 새로운 알고리즘과 복잡한 문제들이 날 쉴새없이 괴롭혔고, 맞고 견디며 점점 강해져 온 것 같다.

  • 손가락 아픈 무시무시한 빡구현 문제부터,

  • 지겹게, 그리고 어렵게 나오는 DP,

  • 항상 새로움을 선사하는 누적 합과 투포인터,

  • 한 번 만들어둔 뒤 몇 번이고 쓸 수 있었던 분리 집합,

  • 위상수학과는 별 관련 없어보이는 위상 정렬,

  • 엄청난 속도를 보여줬던 비트마스킹,

  • 이따금씩 괴롭혔던 최장 증가 부분 수열,

  • 구현법이 맨날 기억 안나던 최소 신장 트리,

  • 만들어 놓고도 신기했던 선분 교차 판정,

  • 늘 거듭제곱을 도와줬던 분할 정복,

  • lower_bound 와 upper_bound 로 다 해먹었던 이분 탐색,

  • 컴퓨터로 하는 노가다의 진수를 보여준 백트래킹,

  • 그리고 소수 빨리 찾아주는 에라토스테네스의 체까지…

정말 많은 것들을 배우고 써볼 수 있던 여정인 것 같다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/17404

← Previous Post Next Post →